1. Field of the Invention
The present invention generally relates to a pre-encoding and pre-decoding apparatuses and methods thereof, and more particularly, to the pre-encoding and pre-decoding apparatuses and the methods thereof which are adapted for an orthogonal frequency-division multiplexing (OFDM) system.
2. Description of Related Art
In a communication field, an encoding technology is used for compressing a length of a transmitted signal, or for protecting the transmitted signal so as to reduce errors caused by the transmission. As the detection theory is being developed, equalization technologies and noise estimation methods are gradually becoming sophisticated. Therefore, the receiver end now is capable of estimating what the data to be received would be according to the characteristic of the transmission channel.
Supposing a receiver receives a signal y=Hx+n, wherein y represents a received signal vector, and y=[y1,y2, . . . ,ym]T; x represents a signal vector transmitted by a transmitter, and x=[x1,x2, . . . ,xm]T; n represents a noise vector, and n=[n1,n2, . . . ,nm]T; H represents a channel response matrix, and is defined as:
      H    =          [                                                  h                              1                ,                1                                                                        h                              1                ,                2                                                          …                                …                                              h                              1                ,                m                                                                                        h                              2                ,                1                                                                        h                              2                ,                2                                                          …                                …                                              h                              2                ,                m                                                                                        h                              3                ,                1                                                                        h                              3                ,                2                                                          …                                …                                              h                              3                ,                m                                                                          ⋮                                ⋮                                ⋰                                ⋰                                ⋮                                                              h                              m                ,                1                                                                        h                              m                ,                2                                                          …                                …                                              h                              m                ,                m                                                        ]        ,wherein hi,j represents a channel response of a transmitted signal xj to a received signal yi.
In general, a best solution {circumflex over (x)} (i.e. a solution with a lowest error rate) can be obtained by a method of maximum a posteriori (MAP) estimation, wherein {circumflex over (x)} is defined as:
      x    ^    =                    arg        ⁢                                  ⁢        max            x        ⁢                  ⁢                  p        ⁡                  (                      y            |            x                    )                    .      After deduction {circumflex over (x)} can be represented as:
            x      ^        =                                        arg            ⁢                                                  ⁢            min                    x                ⁢                                                            1                                  2                  ⁢                                      σ                    n                    2                                                              ⁡                              [                                  y                  -                  Hx                                ]                                      T                    ⁡                      [                          y              -              Hx                        ]                              -              ln        ⁢                                  ⁢                  p          ⁡                      (            x            )                                ,wherein σn2 represents a power of the noise, and p(x) represents a probability of transmitting x. In other words, finding an x lets
                              1                      2            ⁢                          σ              n              2                                      ⁡                  [                      y            -            Hx                    ]                    T        ⁡          [              y        -        Hx            ]        -      ln    ⁢                  ⁢          p      ⁡              (        x        )            achieve a minimum value correspondingly. And in this manner, the solved x is the best solution {circumflex over (x)}. If each outcome of x has the equivalent probability, then the above equation becomes
            x      ^        =                                                      arg              ⁢                                                          ⁢              min                        x                    ⁡                      [                          y              -              Hx                        ]                          T            ⁡              [                  y          -          Hx                ]              ,which is a solution of a maximum likelihood (ML). However, no matter the MAP method or the ML method, its computation complexity to obtain the solution is very high. Suppose to transmit a binary phase shift keying (BPSK), and comparing each outcome of x, there is a computation complexity of O(2m). As such, even though theoretical best solutions are exemplified above, the computation complexity thereof is very high, as such can be rarely put in use.
Further, in order to reduce the computation complexity, the receiver may implement a linear detection method. Typical linear detection methods include zero forcing (ZF) equalization technology and minimum mean square error (MMSE) equalization technology.
When the receiver adopts a ZF equalization technology, the solved signal is {circumflex over (x)}=H−1y, which computation complexity is O(m3). In this manner, although the computation complexity can be reduced by adopting the ZF equalization technology, a correction rate of the solved {circumflex over (x)} is not as high as when using the ML method.
When the receiver adopts an MMSE equalization technology, the solved signal is {circumflex over (x)}= Wy, wherein the matrix W can be represented as
      W    _    =                    arg        ⁢                                  ⁢        min            W        ⁢                                                  x            -            Wy                                    2            .      That is to find a matrix W, by which a sum of a mean square deviation of a solved {circumflex over (x)} and the originally transmitted signal x is minimum. The matrix W=RxyRy−1 can be obtained by a differential approach, wherein Ryx=E[xyT], Ry=E[yyT]. Accordingly, an equation
      W    _    =                    (                                            H              *                        ⁢            H                    +                                    σ              n                                      σ              x                                      )                    -        1              ⁢          H      *      can be obtained by summarizing the above equations, wherein I represents an identity matrix, while σn2 and σx2 respectively represent powers of the transmitted signal x and the noise n. The solved signal {circumflex over (x)} by the MMSE equalization technology has a higher correction rate than the ZF equalization technology, and has a complexity of O(m3). However, the correction rate thereof is still not as high as when using the ML method.
In order to enhance the correction rate of the receiver, methods of iterative detection have been proposed. Currently, they typically include vertical Bell Labs layered space-time (VBLAST) detection method, iterative multi-user detection (MUD) method, and sphere decoding method.
The VBLAST detection method is developed by Bell Labs. The VBLAST detection method is mainly applied in multiple input multiple output (MIMO) communication systems or space time multiplexing communication systems. Besides the MMSE estimation, the VBLAST detection method further adopts an interference cancellation approach to enhance the entire performance thereof, so that it can achieve a performance better than those of the ZF and MMSE equalization technologies.
The VBLAST detection method firstly uses the MMSE method for estimating {circumflex over (x)}0=ZTy, wherein ZT is a coefficient matrix of MMSE. Then, a {circumflex over (x)}k0 having a maximum signal to noise ratio (SNR) is found out from {circumflex over (x)}0. Then, sgn({circumflex over (x)}k0) can be obtained by a hard decision, wherein sgn(•) is an operator for a sign operator, and when {circumflex over (x)}k0>0, sgn({circumflex over (x)}k0)=1, and when {circumflex over (x)}k0<0, sgn({circumflex over (x)}k0)=−1. Then, after cancelling the interfering items, an equation of y1=y−sgn({circumflex over (x)}k0)·HEk0 can be obtained, wherein Ej is a N×1 matrix, and its all elements other than the jth are 0. When the noise is further considered, then the equation becomes y1=Hx−sgn({circumflex over (x)}k0)·HEk0+n, and an MMSE computation is repeated to obtain {circumflex over (x)}1=ZTy1. Then, a maximum element {circumflex over (x)}k1 having a maximum SNR is found out from {circumflex over (x)}1, and a hard decision is made to obtain sgn({circumflex over (x)}k1). Then, interfering items are cancelled to obtain y2=y1−sgn({circumflex over (x)}k1)·HEk1. The foregoing steps are repeated until all elements of x are determined by hard decisions. Accordingly, a VBLASAT requires m times MMSE estimations, so that it is featured with a computation complexity of O(m4). In this manner, although it has a higher complexity than MMSE and ZF, the VBLAST has a performance much better than MMSE and ZF.
In another hand, a receiver implementing an iterative MUD method is to find out a vector wk=argwkmin∥xk−wkT(y−H{right arrow over (x)}k))∥2, and relies upon wk to obtain {circumflex over (x)}k, wherein {right arrow over (x)}k=[{circumflex over (x)}1 {circumflex over (x)}2 . . . {circumflex over (x)}k−1 0 {circumflex over (x)}k+1 . . . {circumflex over (x)}m]. Therefore, wk is used to solve
                    x        ^            k        =          tanh      ⁡              (                              2            ⁢                          z              k                                            1            -                          u              k                                      )              ,wherein zk=Ry,k{ wkT(y−H{right arrow over (x)}k)}, wk=Ry,k−1hk, uk=hkHRy,k−1hk, Ry,k=hkhkT+HE[{right arrow over (x)}{right arrow over (x)}H]HH+σn2I. The receiver which implements such an iterative MUD has a higher correction rate than the VBLAST, and its computation complexity is O(m4).
Furthermore, in order to obtain the best solution and to improve the decoding correction rate of the receiver, the receiver may alternatively adopt a sphere decoding method. A receiver implementing the sphere decoding method finds out {circumflex over (x)}=argx′min|y−Hx′|, (i.e. find out (x−{circumflex over (x)})HHH(x−{circumflex over (x)})≦r2), wherein r represents a searching radius for sphere decoding. Then the receiver implementing the sphere decoding method obtains the final best solution according to an iterative computation. Although the receiver implementing such a sphere decoding method has a higher correction rate than the receiver implementing an iterative MUD method, the computation complexity of the receiver is a non-deterministic polynomial time complete (NPC) problem.
The above iterative detection method may allow the receiver to obtain a better correction rate, however the computation complexity thereof is not as low as that of the linear detection method. Hence, the computation complexity of the iterative detection method is not good for real time transmission, e.g., video streaming. As to the linear detection method, it has a so low correction rate that is not suitable for transmission channels under bad conditions. As such, the present invention provides a pre-encoding apparatus and a pre-decoding apparatus. The pre-encoding apparatus and the pre-decoding apparatus are adapted for a communication system, and the pre-decoding apparatus is featured with a lower computation complexity and is adapted to decode the received signal to obtain a signal with a lower error rate.